package com.heima.leetcode.practice;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 559. N 叉树的最大深度
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/18 9:31
 */
public class E559 {

    /**
     * <h3>方法一：递归结合流，效率慢</h3>
     * @param root 根节点
     * @return 最大深度
     */
    public int maxDepth1(Node root) {
        // 当前树是空，返回0
        if (root == null){
            return 0;
        }
        // 得到当前树根节点的孩子节点
        List<Node> children = root.children;
        // 如果没有孩子，返回1，主要是避免空指针
        if (children == null){
            return 1;
        }else {
            return children.stream()
                    .map(this::maxDepth1)
                    .max(Comparator.comparingInt(o -> o))
                    .orElse(0) + 1;
        }
    }

    /**
     * <h3>方法二：迭代</h3>
     * @param root 根节点
     * @return 最大深度
     */
    public int maxDepth2(Node root) {
        if (root == null) {
            return 0; // 空树深度为 0
        }

        int maxDepth = 0;
        Node curr = root;
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> depths = new LinkedList<>(); // 用于记录每个节点的深度

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                // 深度入栈
                if (depths.isEmpty()) {
                    depths.push(1); // 初始深度为 1
                } else {
                    depths.push(depths.peek() + 1); // 当前节点深度为父节点深度 + 1
                }
                // 处理当前节点的第一个子节点
                if (curr.children != null && !curr.children.isEmpty()) {
                    curr = curr.children.get(0);
                } else {
                    curr = null;
                }
            } else {
                // 当前节点为 null，处理栈顶元素
                Node last = stack.pop();
                int depth = depths.pop(); // 获取当前节点的深度

                // 更新最大深度
                maxDepth = Math.max(maxDepth, depth);

                // 获取父节点
                Node parent = stack.peek();
                if (parent != null) {
                    int index = indexOf(parent, last);
                    // 如果有更多的子节点，遍历下一个
                    if (index < parent.children.size() - 1) {
                        curr = parent.children.get(index + 1);
                    } else {
                        curr = null; // 如果没有更多的子节点，设置为 null
                    }
                } else {
                    curr = null; // 如果没有父节点，设置为 null
                }
            }
        }
        return maxDepth;
    }

    /**
     * <h3>方法三：递归正常处理，效率最高</h3>
     * @param root 根节点
     * @return 最大深度
     */
    public int maxDepth3(Node root) {
        // 递归结束条件：当前节点为空，返回0
        if (root == null){
            return 0;
        }
        // 没有子树，不必要递归处理
        if (root.children == null || root.children.isEmpty()){
            return 1;
        }
        int maxDepth = 0;
        // 递的时候求当前节点的每个子树之间的最大深度
        for (Node child : root.children) {
            int childDepth = maxDepth3(child);
            maxDepth = Math.max(maxDepth, childDepth);
        }
        // 返回当前节点深度
        return maxDepth + 1;
    }

    private int indexOf(Node parent, Node child) {
        if (parent == null) {
            return -1;
        }
        for (int i = 0; i < parent.children.size(); i++) {
            if (parent.children.get(i) == child) {
                return i;
            }
        }
        return -1;
    }
}
